package code.classic150on2025;

import java.util.*;

public class TheInterval {
    // 56. 合并区间
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        List<int[]> list = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        int len = intervals.length;
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] > end) {
                list.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                end = Math.max(end, intervals[i][1]);
            }
        }
        list.add(new int[]{start, end});
        int ansSize = list.size();
        int[][] ans = new int[ansSize][2];
        for (int i = 0; i < ansSize; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    // 57. 插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0)
            return new int[][]{newInterval};
        int len = intervals.length;
        List<int[]> small = new ArrayList<>();
        List<int[]> big = new ArrayList<>();
        int start = newInterval[0], end = newInterval[1];
        for (int i = 0; i < len; i++) {
            if (intervals[i][1] < start) {
                small.add(new int[]{intervals[i][0], intervals[i][1]});
            } else if (intervals[i][0] > end) {
                big.add(new int[]{intervals[i][0], intervals[i][1]});
            } else {
                start = Math.min(start, intervals[i][0]);
                end = Math.max(end, intervals[i][1]);
            }
        }
        int total = small.size() + big.size() + 1;
        int[][] ans = new int[total][2];
        int pos = 0;
        for (int[] s : small)
            ans[pos++] = s;
        ans[pos++] = new int[]{start, end};
        for (int[] b : big)
            ans[pos++] = b;
        return ans;
    }

    // 452. 用最少数量的箭引爆气球
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int len = points.length;
        int start = points[0][0], end = points[0][1];
        int count = 0;
        for (int i = 1; i < len; i++) {
            if (end < points[i][0]) {
                count++;
                start = points[i][0];
                end = points[i][1];
            } else {
                start = points[i][0];
                end = Math.min(end, points[i][1]);
            }
        }
        return count + 1;
    }
}
